package com.ocean.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode.cn/problems/maximum-depth-of-binary-tree/
 * 二叉树的最大深度
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/10 <br>
 */
public class MaximumDepthOfBinaryTree {

    public static void main(String[] args) {
        MaximumDepthOfBinaryTree tree = new MaximumDepthOfBinaryTree();
        System.out.println(tree.maxDepth(TreeNode.getRoot()));
    }

    /**
     * 使用层次遍历的方法
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int max = 0;
        while (!deque.isEmpty()) {
            // 全部拿出来
            max++;
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.poll();
                if (node.getLeft() != null) {
                    deque.offer(node.getLeft());
                }
                if (node.getRight() != null) {
                    deque.offer(node.getRight());
                }
            }
        }
        return max;
    }
}
